package com.itheima.datastructure.binarysearchtree;

import com.itheima.datastructure.binarysearchtree.binarytree.TreeNode;

import java.util.LinkedList;

public class E05Leetcode938 {
    //解法1：中序遍历非递归实现
    public int rangeSumBST1(TreeNode node,int low,int high){
        TreeNode p=node;
        LinkedList<TreeNode> stack=new LinkedList<>();
        int sum=0;
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p=p.left;
            }else{
                TreeNode pop=stack.pop();
                if(pop.val>high){
                    break;
                }
                if(pop.val>=low && pop.val<=high){
                    sum+=pop.val;
                }
                p=pop.right;
            }
        }
        return sum;
    }

    //解法2：上下限递归
    public int rangeSumBST2(TreeNode node, int low,int high){
        if(node==null){
            return 0;
        }
        //不满足情况就继续递归
        if(node.val<low){
            return rangeSumBST2(node.right,low,high);
        }
        if(node.val>high){
            return rangeSumBST2(node.left,low,high);
        }
        //在范围内
        return  node.val+rangeSumBST2(node.left,low,high)+rangeSumBST2(node.right,low,high);
    }
}
